import collections
class Solution(object):
    def gridIllumination(self, n, lamps, queries):
        heng_set = collections.defaultdict(set)
        zong_set = collections.defaultdict(set)
        xie_set1 = collections.defaultdict(set)
        xie_set2 = collections.defaultdict(set)
        for x, y in lamps:
            heng_set[x].add((x, y))
            zong_set[y].add((x, y))
            xie_set1[y - x].add((x, y))
            xie_set2[y + x].add((x, y))
        ans = []
        for x, y in queries:
            if heng_set[x] or zong_set[y] or xie_set1[y - x] or xie_set2[x + y]:
                ans.append(1)
            else:
                ans.append(0)
            for ux in range(x - 1, x + 2):
                for uy in range(y - 1, y + 2):
                    if 0 <= ux < n and 0 <= uy < n:
                        if (ux, uy) in heng_set[ux]:
                            heng_set[ux].remove((ux, uy))
                        if (ux, uy) in zong_set[uy]:
                            zong_set[uy].remove((ux, uy))
                        if (ux, uy) in xie_set1[uy - ux]:
                            xie_set1[uy - ux].remove((ux, uy))
                        if (ux, uy) in xie_set2[ux + uy]:
                            xie_set2[ux + uy].remove((ux, uy))
        return ans





data = Solution()
n = 5
lamps = [[0, 0], [0, 4]]
queries = [[0, 4], [0, 1], [1, 4]]
print(data.gridIllumination(n, lamps, queries))
